#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
ll ans=0,m,cur;
class Node {
public:
	ll val;
	Node* left;
	Node* right;
	int height;
	Node(ll val_) :val{ val_ }, height{0},left{nullptr},right{nullptr}{}
	Node(ll val_,Node* left_,Node* right_):val{val_},left{left_},right{right_}{}
};
int getheight(Node* root) {
	if (root == nullptr) return -1;
	else return root->height;
}

Node* LL(Node* root){
	auto lt = root->left;
	root->left = lt->right;
	lt->right = root;
	root->height = max(getheight(root->left),getheight(root->right)) + 1;
	lt->height = max(getheight(lt->left),root->height)+1;
	return lt;
}
Node* RR(Node* root) {
	auto rt = root->right;
	root->right = rt->left;
	rt->left = root;
	root->height = max(getheight(root->left),getheight(root->right)) + 1;
	rt->height = max( getheight(rt->right),root->height)+ 1;
	return rt;
}
Node* LR(Node* root) {
	root->left = RR(root->left);
	return LL(root);
}
Node* RL(Node* root) {
	root->right = LL(root->right);
	return RR(root);
}
//
Node* insert(Node* root, ll v) {
	if (!root) {
		root = new Node{ v };
	}
	else if (v < root->val) {
		cur=min(cur,root->val-v);
		root->left = insert(root->left, v);
		if (getheight(root->left) - getheight(root->right) == 2) {
			if (v < root->left->val) {
				root = LL(root);
			}
			else if (v > root->left->val) {
				root = LR(root);
			}
		}
	}
	else if (v > root->val) {
		cur=min(cur,v-root->val);
		root->right = insert(root->right, v);
		if (getheight(root->right) - getheight(root->left) == 2) {
			if (v > root->right->val) {
				root = RR(root);
			}
			else if (v < root->right->val) {
				root = RL(root);
			}
		}
	}
	else{
		cur=0;
	}
	root->height = max(getheight(root->left), getheight(root->right)) + 1;
	return root;
}

int main(){
	scanf("%d",&n);
	Node* root=nullptr;
	for(int i=0;i<n;i++){
		scanf("%lld",&m);
		if(root==nullptr){
			ans+=m;
			root=insert(root,m);
			continue;
		}
		cur=LLONG_MAX;
		root=insert(root,m);
		ans+=cur;
	}
	printf("%lld",ans);
	return 0;
}

